package vip.zhenzicheng.algorithm.leetcode.stack_queue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.cn/problems/basic-calculator/">基本计算器 [困难]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-24 13:53
 */
public class BasicCalculator_224 {

  public int calculate(String s) {
    int result = 0;
    int num = 0; // 存放当前待计算数字
    int sign = 1; // 计算符号 +1/-1
    Deque<Integer> stack = new LinkedList<>();

    char[] chars = s.toCharArray();
    int len = chars.length;

    for (int i = 0; i < len; i++) {
      char c = chars[i];
      if (c == ' ') {
        continue;
      }
      // 判断是否为数字
      if (c >= '0' && c <= '9') {
        num = num * 10 + (c - '0'); // 转换为数字
        if (i < len - 1 && chars[i + 1] >= '0' && chars[i + 1] <= '9') {
          continue;
        }
      } else if (c == '+' || c == '-') {
        num = 0;
        sign = c == '+' ? 1 : -1; // 判断符号位
      } else if (c == '(') {
        stack.push(result); // 结果入栈
        stack.push(sign); // 符号入栈
        result = 0;
        sign = 1;
      } else if (c == ')') { // 开始合并计算
        sign = stack.pop();
        num = result;
        result = stack.pop();
      }
      result += sign * num; // 合并计算结果
    }
    return result;
  }
}
